package com.zjj.algorithm.learning.leetcode.linkedlist;

import java.util.Arrays;

/**
 * 23. 合并K个升序链表 困难题
 * 给你一个链表数组，每个链表都已经按升序排列。
 * <p>
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 * 示例 1：
 * <p>
 * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
 * 输出：[1,1,2,3,4,4,5,6]
 * 解释：链表数组如下：
 * [
 * 1->4->5,
 * 1->3->4,
 * 2->6
 * ]
 * 将它们合并到一个有序链表中得到。
 * 1->1->2->3->4->4->5->6
 * 示例 2：
 * <p>
 * 输入：lists = []
 * 输出：[]
 * 示例 3：
 * <p>
 * 输入：lists = [[]]
 * 输出：[]
 *
 * @author zjj_admin
 * @date 2022/11/25 14:33
 */
public class MergeSortedLists {

    public static void main(String[] args) {


        ListNode node1 = new ListNode(3, null);
        ListNode node2 = new ListNode(0, node1);
        ListNode node3 = new ListNode(4, node2);
        ListNode node4 = new ListNode(1, null);
        ListNode node5 = new ListNode(3, node4);
        ListNode node6 = new ListNode(1, node5);
        ListNode node7 = new ListNode(4, null);
        ListNode node8 = new ListNode(0, node7);
        ListNode node9 = new ListNode(2, node8);

        ListNode[] listNodes = new ListNode[]{node9, node6, node3};
        ListNode res = mergeLists(listNodes);
        System.out.println("res = " + res);
    }

    /**
     * 使用归并排序
     * <p>
     * 时间
     * 1 ms
     * 击败
     * 100%
     * 内存
     * 42.4 MB
     * 击败
     * 98.12%
     *
     * @param lists
     * @return
     */
    public static ListNode mergeLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        return merge2Lists(lists, 0, lists.length - 1);
    }

    private static ListNode merge2Lists(ListNode[] lists, int start, int end) {
        if (start == end) {
            return lists[start];
        }
        int mid = start + (end - start) / 2;
        ListNode left = merge2Lists(lists, start, mid);
        ListNode right = merge2Lists(lists, mid + 1, end);
        return merge1(left, right);
    }


    /**
     * 这个方法合并的是两个有序的链表
     *
     * @param left
     * @param right
     * @return
     */
    private static ListNode merge1(ListNode left, ListNode right) {

        ListNode dummyHead = new ListNode(-1);
        ListNode pre = dummyHead;
        while (left != null && right != null) {
            if (left.val <= right.val) {
                pre.next = new ListNode(left.val);
                left = left.next;
            } else {
                pre.next = new ListNode(right.val);
                right = right.next;
            }
            pre = pre.next;
        }
        if (left != null) {
            pre.next = left;
        }
        if (right != null) {
            pre.next = right;
        }
        return dummyHead.next;

    }
}
